/*public class test {
}*/
/*
import java.math.BigInteger;

public class KaratsubaMultiplication {
    // Karatsuba分治递归函数
    private static BigInteger karatsuba(BigInteger x, BigInteger y) {
        int n = Math.max(x.bitLength(), y.bitLength());
        // 终止条件：位数≤1，直接相乘
        if (n <= 1) {
            return x.multiply(y);
        }

        // 拆分：取n/2位作为分段点
        n = (n + 1) / 2;
        BigInteger tenPowerN = BigInteger.TEN.pow(n);
        BigInteger tenPower2N = BigInteger.TEN.pow(2 * n);

        // 拆分x为x1（高位）、x0（低位）
        BigInteger x1 = x.divide(tenPowerN);
        BigInteger x0 = x.mod(tenPowerN);
        // 拆分y为y1（高位）、y0（低位）
        BigInteger y1 = y.divide(tenPowerN);
        BigInteger y0 = y.mod(tenPowerN);

        // 求解：递归计算3个小乘积
        BigInteger p1 = karatsuba(x1, y1);
        BigInteger p0 = karatsuba(x0, y0);
        BigInteger p2 = karatsuba(x1.add(x0), y1.add(y0));

        // 合并：p1*10^(2n) + (p2-p1-p0)*10^n + p0
        return p1.multiply(tenPower2N)
                .add(p2.subtract(p1).subtract(p0).multiply(tenPowerN))
                .add(p0);
    }

    // 入口方法
    public static BigInteger multiply(String num1, String num2) {
        BigInteger x = new BigInteger(num1);
        BigInteger y = new BigInteger(num2);
        return karatsuba(x, y);
    }

    // 测试
    public static void main(String[] args) {
        String a = "12345678901234567890";
        String b = "98765432109876543210";
        System.out.println("乘积：" + multiply(a, b));
    }
}*/
import java.math.BigInteger;

public class KaratsubaMultiplication {
    // Karatsuba 分治递归函数
    private static BigInteger karatsuba(BigInteger x, BigInteger y) {
        int n = Math.max(x.bitLength(), y.bitLength());
        // 终止条件：当位数小于等于 2 时，直接使用 BigInteger 的 multiply 方法计算
        if (n <= 2) {
            return x.multiply(y);
        }

        // 计算拆分的位置，将 n 向上取半
        n = (n + 1) / 2;
        BigInteger tenPowerN = BigInteger.TEN.pow(n);
        BigInteger tenPower2N = BigInteger.TEN.pow(2 * n);

        // 拆分 x 为 x1（高位部分）和 x0（低位部分）
        BigInteger x1 = x.divide(tenPowerN);
        BigInteger x0 = x.mod(tenPowerN);
        // 拆分 y 为 y1（高位部分）和 y0（低位部分）
        BigInteger y1 = y.divide(tenPowerN);
        BigInteger y0 = y.mod(tenPowerN);

        // 递归计算三个小乘积
        BigInteger p1 = karatsuba(x1, y1);
        BigInteger p0 = karatsuba(x0, y0);
        BigInteger p2 = karatsuba(x1.add(x0), y1.add(y0));

        // 合并结果：p1*10^(2n) + (p2 - p1 - p0)*10^n + p0
        return p1.multiply(tenPower2N)
                .add(p2.subtract(p1).subtract(p0).multiply(tenPowerN))
                .add(p0);
    }

    // 入口方法，接收字符串形式的大整数
    public static BigInteger multiply(String num1, String num2) {
        BigInteger x = new BigInteger(num1);
        BigInteger y = new BigInteger(num2);
        return karatsuba(x, y);
    }

    // 测试方法
    public static void main(String[] args) {
        String a = "12345678901234567890";
        String b = "98765432109876543210";
        System.out.println("Karatsuba 算法计算结果：" + multiply(a, b));
        // 用 BigInteger 自带的 multiply 方法验证结果
        BigInteger bigA = new BigInteger(a);
        BigInteger bigB = new BigInteger(b);
        System.out.println("BigInteger 自带方法计算结果：" + bigA.multiply(bigB));
    }
}